<html lang="en">
<head>
<meta name="viewport" content="width=device-width, initial-scale=1.0">
<meta http-equiv="Content-Type" content="text/html; charset=utf-8">

<link type="text/css" rel="stylesheet" href="../source/css/bootstrap.css" />
<link type="text/css" rel="stylesheet" href="../source/css/bootstrap-responsive.css" />
<link type="text/css" rel="stylesheet" href="../source/css/docs.css" />
<link type="text/css" rel="stylesheet" href="../source/css/monokai.css" />
<link type="text/css" rel="stylesheet" href="../source/css/font-awesome.css">

<script type="text/javascript" src="../source/js/jquery-1.9.1.js"></script>
<script type="text/javascript" src="../source/js/bootstrap.js"></script>
<script type="text/javascript" src="../source/js/highlight.pack.js"></script>
<script type="text/x-mathjax-config"> 
    MathJax.Hub.Config({ 
        tex2jax: {inlineMath: [['$','$'], ['\\(','\\)']]} 
    }); 
</script>
<script type="text/javascript"
    src="http://cdn.mathjax.org/mathjax/latest/MathJax.js?config=TeX-AMS-MML_HTMLorMML">
</script>
<title>Network</title>

</head>
<body data-spy="scroll" data-target=".bs-docs-sidebar">
<div class="navbar navbar-fixed-top">
    <div class="navbar-inner">
        <div class="container">
            <!-- .btn-navbar is used as the toggle for collapsed navbar content -->
            <a class="btn btn-navbar" data-toggle="collapse" data-target=".nav-collapse">
                <span class="icon-bar"></span>
                <span class="icon-bar"></span>
                <span class="icon-bar"></span>
            </a>

            <!-- Be sure to leave the brand out there if you want it shown -->
            <a class="brand" href="../index.html">Wahacer's blogs</a>

            <!-- Everything you want hidden at 940px or less, place within here -->
            <div class="nav-collapse collapse">
                <!-- .nav, .navbar-search, .navbar-form, etc -->
                <ul class="nav">
                    <li class="">
                        <a href="../index.html">Index</a>
                    </li>
                    
                    <li class="">
                        <a href="../Solution/index.html">Solution</a>
                    </li>
                    
                    <li class="">
                        <a href="../Algorithm/index.html">Algorithm</a>
                    </li>
                    

                </ul>
            </div>
        </div>
    </div>
</div>

<div class="container-fluid">
    <div class="row-fluid">
        <!--　侧边拦 -->
        <div class="span2 bs-docs-sidebar">
            <br><br><br>
            <div align="center"><img src="../source/picture/photo.jpg" alt="photo" width="250" height="250" /></div>
            <p align="center"><strong>Wahacer</strong></p>

        </div>

        <!-- 主内容　-->
        <div class="span8">
            <br>
            <!--Body content-->
            <h1 id="toc-0">网络流</h1>
<h4 id="toc-1">定义</h4>
<p><strong>有向图</strong>G=（V,E）中：</p>
<p>有唯一的一个源点S和汇点T，每一个图都有一个非负容量Cu,v</p>
<p>满足上述条件的图G称为网络流图（又称网络），记为G=（V,E,C）</p>
<h3 id="toc-2">流</h3>
<p>对于网络流图G=（V,E,C）的每一条边（u，v），给定一个数fu，v，且满足下列条件:</p>
<p>1、运量不能超过容量</p>
<p>2、除源点和汇点外，其余顶点v恒有流入=流出</p>
<p>这时G=（V,E,C）中的流称为G的可行流f</p>
<p>为了方便和出于对称性，我们认为：fu，v=-fv，u</p>
<p>当所有的f都为0时，那么就称f为零流，零流一定是可行流。</p>
<p>网络流的流量w=流向终点的流量。</p>
<h2 id="toc-3">求解最大流</h2>
<p>只要不断地在现有的流网络上累加小的流，当不能累加的时候就得到了最大流。</p>
<p>如果现有的流并不是最大流的一部分，是否还能累加形成最大流呢？</p>
<p>可以，因为流是会与相反方向的流相互抵消的，我们可以发现，通过不同的流之间的叠加，我们可以通过回溯之前的流的部分路段，从而修正得到正确的选择。</p>
<p>所以之前的对称性得到了应用。</p>
<h2 id="toc-4">切割</h2>
<p>定义：设G=（V,E,C）是一直的网络流图，假定s是V的一个子集，s'是s的补集，这样把顶点集V分成s和s'两个部分，满足S∈ s，T∈ s'</p>
<p>对于一个端点在s，另一个端点在s'的所有边的集合，叫做网络流图G的一个切割，用（s,s'）表示。</p>
<p>切割容量：在切割中，把所有边容量和叫做这个切割的容量。</p>
<p>[C<em>{s,s'}=\sum</em>{u \in s,v \in s'}C_{u,v}]</p>
<p>净流量f(s,s')：横跨切割(s,s')流量的代数和。  -净流量的值=当前的流量W</p>
<p>[f<em>{s,s'}=\sum</em>{u \in s,v \in s'}f<em>{u,v}-\sum</em>{u \in s, v \in s'}f_{v,u}]</p>
<h2 id="toc-5">最大流-最小割定理</h2>
<p>引：对于已知的网络流图，从源点s到汇点t的流量w的最大值小于等于任何一个切割的容量，记</p>
<p>[ W<em>{max} \leq min(C</em>{s,s'}) ]</p>
<p>最大流最小割定理(Ford-Fulkerson定理)：</p>
<p>在一个给定的网络流图上，流的最大值等于切割容量的最小值，即</p>
<p>[ W<em>{max}=minC</em>{s,s'}]</p>
<h3 id="toc-6">证明：</h3>
<p>在网络流图G=（V,E,C）中，定义从源点S到汇点T的道路：设（V0=S,V1,V2,V3……Vn=T）为G上的顶点序列，对于i=0,1,2……n-1，都有（Vi,Vi+1）或(Vi+1,Vi)属于E，则称(V0,V1,V2,……Vn)是一条从S到T的道路。</p>
<p>由于G是有向图，道路上边的方向与道路方向一致的边称为前向边P+，反之称为后向边P-。</p>
<p>道路上边的饱和：前向边若fu,v=Cu,v，后向边若fu,v=0（对称性），则称边(u,v)为关于该条道路上的饱和边。</p>
<p>若从S到T的道路上所有的边均不饱和，即对于P+有fu,v&lt;Cu,v，P-有fu,v&gt;0，则称这条边为可增广道路。</p>
<p>修改可增广道路上每条边的流量，同时保持网络流的可行性，达到流量的增加，其增量的确定方法如下：</p>
<p>令</p>
<p>[ \delta(u,v)=\begin{cases} C<em>{u,v} - f</em>{u,v} , P+\ f_{u,v'} , P- \end{cases} ]</p>
<p>取δ=min{δ(u,v)}为增量。</p>
<p>然后对可增广路的每一条前向边流量增加δ，每一套后向边减少δ，从而使得整个网络流的流量增加。</p>
<p>设网络流图G的流量f达到最大，我们构造一个点的集合s如下：</p>
<ul>
<li><p>(S \in s)</p>
</li>
<li><p>(x \in s , f<em>{x,y} &lt; C</em>{x,y}  - &gt; y \in s)</p>
</li>
<li><p>(x \in S , f_{y,x} &gt; 0 -&gt; y \in s)</p>
</li>
</ul>
<p>由此可见，s就是从S出发、有空余流量的边所关联的点击，因此T ∉ s，否则S到T不饱和，f不是最大流。</p>
<p>设s'是s的补集，那么T ∈ s' ，我们构造出了一个切割(s,s').</p>
<p>按照s的定义，若 x ∈ s, y ∈ s' , 则fx,y=Cx,y , fy,x=0</p>
<p>所以</p>
<p>[W<em>{max}=\sum(f</em>{x,y}-f<em>{y,x}) = \sum f</em>{x,y} = C_{s,s'}]</p>
<p>即：已证明最大流-最小割定理</p>
<h2 id="toc-7">求解最大流</h2>
<p>我们已经证明了算法的正确性。每次新增一条刘鹗的时候，我们都要满足每条边的容量限制。即当前这条边的流量加上新的流量，不能超过边的剩余流量限制。</p>
<p>一个便捷的处理方式就是：记录这条边还能容纳的流量，即边的容量加上能够被回溯（对称边）的流量，称为"残存容量"。将所有的残存容量看成一个残存网络，也就是一个新的网络流问题，我们在新的图上继续寻找不饱和路径。</p>
<p>我们要做的就是记录每条边和它的反向边（对称性）以及每条边的剩余容量，写一个dfs每次寻找不饱和路径并修改容量，找不到时退出。此时我们得到了最大流。</p>
<p>使用dfs时间复杂度O(E)，设最大流的流量为w，由于每次流量最少+1，所以时间复杂度为O（Ew）</p>
<p>但是由于该算法（FF）每次只增广一条路径，缺点就是当最大流量较大时，寻找的路径错误可能使运行时间变长，出现反复增广。</p>
<p>当我们用bfs优化FF时，就得到了一个新的算法（EK），每次寻找残存网络上S到T的最短路径</p>
<p>所以时间复杂度为</p>
<p>[O(VE^2)]</p>
<p>为了加快算法的运行时间我们需要一次增广多条路径，就得到了Dinic算法。</p>
<p>每次对残存网络bfs标记每个点距离S的深度(容量有剩余的边才会出现在残余网络上)，dfs的时候只对与当前点有边且深度大1的点继续增广。</p>
<p>记录当前顶点u，以及到目前为止剩余能分配的容量limit。</p>
<p>每次更新完之后，残余网络上所有源点到汇点的最短路径都被阻塞。所以，最多只要V次更新就可以找到最大流。</p>
<p>每次更新时间复杂度为</p>
<p>[O(VE)]</p>
<p>总复杂度为</p>
<p>[O(V^2E)]</p>
<p>实际更快。</p>
<hr>
<h2 id="toc-8">By:Wahacer</h2>
<h2 id="toc-9">资料来源：某学姐的ipad~</h2>
<h2 id="toc-10">2017年9月30号</h2>


        </div>
  </div>
</div>
<!-- Footer
    ================================================== -->
<footer class="footer">
  <div class="container">
         Copyright (c) 2017 Powered By <a href="https://gitee.com/uncle-lu/oub">OUB</a>
         <a rel="license" href="http://creativecommons.org/licenses/by-nc-sa/3.0/cn/"><img alt="知识共享许可协议" style="border-width:0" src="https://i.creativecommons.org/l/by-nc-sa/3.0/cn/88x31.png" /></a><br />本作品采用<a rel="license" href="http://creativecommons.org/licenses/by-nc-sa/3.0/cn/">知识共享署名-非商业性使用-相同方式共享 3.0 中国大陆许可协议</a>进行许可。
  </div>
</footer>
<script>
    $('h1').each(function() {
        $(this).wrap('<section id="' + this.id + '"/>');
    });

    $('h1').wrap('<div class="page-header" />');
    $('h1').wrap('<div class="well well-small" />');

    $(document).ready(function() {
        var items = [];
        $('h1').each(function() {
            items.push('<li><a href="#' + this.id + '"><i class="fa fa-chevron-right pull-right"></i> ' + $(this).text() + '</a></li>');
        });  // close each()

    $('#sidebar_list').append( items.join('') );

    $('table').each(function() {
        $(this).addClass('table table-striped table-condensed table-hover');
    });

    $('.done0').each(function() {
        $(this).html('<div class="alert alert-info"><i class="fa fa-check-square-o"></i>'+$(this).html()+'</div></li>');
    });

    $('.done4').each(function() {
        $(this).html('<div class="alert alert-success"><i class="fa fa-square-o"></i>'+$(this).html()+'</div></li>');
    });
   
    $('pre').each(function() {
        $(this).html('<code>'+$(this).html()+'</code>');
    });
    hljs.initHighlightingOnLoad();
});
</script>
</body>
</html>